FIG. 1 (Prior Art) shows a strongly connected directed graph 100 representing a network of routers and allowed links between adjacent routers for an information packet directed to network router H 108. The directed graph 100 illustrates the use of Source-Independent Single-Path routing according to traditional routing schemes like minimum hops or shortest path. Oval shapes represent network routers, also referred to as hosts or “nodes”, that forward information packets from a source device, such as a home computer connected to a node, to a destination device, such as another home computer connected to a node. Shown are node A 101, node B 102, node C 103, node D 104, node E 105, node F 106, node G 107 and node H 108. Also shown are an example information packet source device 109 connected to node E 105 and an example information packet destination device 110 connected to node H 108.
Where an information packet originates from a given source device, it must always first pass through the node to which the source device is connected. This first node will be referred to here as the source router. Where the information packet is destined for a given destination device, the last node the information packet passes through is the node to which the destination device is connected. This last node will be referred to here as the destination router. The destination router can be determined from the packet's destination address using well known network topology protocols. Accordingly, where an information packet originates from source device 109 destined for destination device 110, the source node is node E 105, and the destination node is node H 108. An information packet typically includes destination data from which can be determined the destination device and destination node, as well as source data from which can be determined the source device and source node.
In the directed graph 100, darkened arrows indicate allowed links between nodes for forwarding an information packet to destination node H 108. For any given node which is to forward an information packet to destination node H 108, the information packet will always be forwarded to the same next adjacent node. The next adjacent node forwarded to is also referred to as a “next hop”.
Arrow 111 indicates the link by which node A 101 forwards the information packet to node B 102. Arrow 112 indicates the link by which node B 102 forwards the information packet to node F 106. Arrow 113 indicates the link by which node C 103 forwards the information packet to node G 107. Arrow 114 indicates the link by which node D 104 forwards the information packet to node E 105. Arrow 115 indicates the link by which node E 105 forwards the information packet to node F 106. Arrow 116 indicates the link by which node F 106 forwards the information packet to node H 108. Arrow 117 indicates the link by which node G 107 forwards the information packet to node H 108. Non-darkened arrows illustrate links which are not allowed when the destination node is node H 108. A directed graph of paths to a different destination node would have a different set of allowed and non-allowed links.
Thus, an information packet originating at source device 109 and destined for destination device 110 will first pass to node E 105. Node E 105 will always forward the information packet to next hop node F 106 via link 115. Node F 106 will always forward the information packet to next hop node H 108 via link 116. Node H 108 (the destination node) will then forward the information packet to destination device 110.
As can be seen from the darkened link arrows, there is always a single route from a given node to a given destination node when using this Single-Path routing method. Because the route is determined based on the destination of the information packet, and not determined based on the source of the information packet, the method is referred to as Source-Independent Single-Path routing.
FIG. 2 (Prior Art) is a simplified view of an example node E 105 implementing Source-Independent Single-Path routing. Node E 105 includes a processor 200 and a memory 201. Processor 200 and memory 201 communicate via buses 202 and 203. Memory 201 stores network topology information 204 according to a well-known protocol such as Open Shortest Path First (OSPF) or Intermediate System to Intermediate System (ISIS). An algorithm 205 running on the processor 200 uses the network topology information 204 to determine which adjacent node should be the next hop an information packet takes from node E 105 given the destination node of the information packet. These destination-dependent next hops are stored in memory 201 as the routing table 206 for node E 105.
The algorithm 205 that builds the routing table uses a traditional routing scheme such as minimum hops or shortest path. These traditional routing schemes rely on forwarding a given information packet to a single neighboring router based on its destination for several reasons.
First, the cost of each link between neighboring routers is constant. This link cost is also known as a link metric. Link costs can be based on a link delay or a link transmission time. In the case of hop counting, every link cost is set to be equal. When the link costs change for any reason, so do the routing tables that determine forwarding neighbors. In the algorithm 205 that builds the routing table 206, the cost of a path between the forwarding node 105 and a destination node is determined by adding the costs of the intervening path links. And, the dynamic programming principle of optimality applies, meaning that all sub-paths of a path between the forwarding node 105 and a destination router must be optimal. Determining the cost of a path by adding the costs of the path links is known as the Link Metric Model.
Additionally, it is simple to avoid creating undesirable looping paths or “directed cycles” using Single-Path routing methods. FIG. 3 (Prior Art) is a an expanded view of simplified routing table 206 for node E 105. Row 300 indicates that the next hop when an information packet is destined for destination router H 108 is node F 106. Row 301 indicates that the next hop node when an information packet is destined for destination router F 106 is node F 106.
FIG. 4 (Prior Art) is a simplified view of an example routing table 400 for node F 106, shown for comparison with the example routing table 206 for adjacent node E 105, illustrating the lack of looping, also known as a “directed cycle”, between node E 105 and node F 106. Row 401 indicates that the next hop node when an information packet is destined for destination router H 108 is node H 108. Row 402 indicates that the destination router has been reached when an information packet is destined for destination router F 106. By comparing routing table rows 300 and 301 with routing table rows 401 and 402, it is seen that for instances when the next hop node from node E 105 is node F 106, the next hop node from node F 106 is never node E 105.
In this way, routing tables for adjacent nodes are constructed such that information packets do not follow directed cycles in the Single-Path routing methods. And, because routing table next hops in Single-Path routing methods depend only on the destination of the information packet, and not the source, Single-Path routing methods can be referred to as Source-Independent Single-Path routing. However, problems inherent in Source-Independent Single-Path include over-utilizing, and therefore congesting, the links along optimal paths. Conversely, other links can remain largely underutilized.
In contrast, Multi-Path routing methods can utilize more available links and better avoid link congestion. Known Multi-Path routing methods calculate a set of “best” disjoint paths for an information packet from a particular source to a particular destination node and channel traffic between those two nodes along those paths, in inverse proportion to their costs. Disjoint paths do not share the same set of nodes or links. In a network, this has to be done for every possible pair of source and destination nodes. FIG. 5 (Prior Art) is a directed graph 500 of the network of routers of FIG. 1 (Prior Art) and links between adjacent routers illustrating the use of Source-Dependent Multi-Path routing.
Darkened arrows in the directed graph 500 of a network indicate allowed links between nodes for forwarding an information packet according to Multi-Path routing when the source node is node A 501 and the destination node is node H 508. A Multi-Path routing method would, for example, use not only the path from node A 501 to node B 502 via link 511, then from node B 502 to node F 506 via link 512, and then from node F 506 to node H 508 via link 514, but also the disjoint path from node A 501 to node C 503 via link 517, then from node C 503 to node G 507 via link 513, and then from node G 507 to node H 508 via link 515 to transport packets from source node A to destination node H. Non-darkened arrows illustrate links which are not allowed when the source node is node A 501 and the destination node is node H 508.
Because routing in known methods of Multi-Path routing requires consideration of the source of the information packet in order to prevent paths with directed cycles, known Multi-Path routing methods can be referred to as Source-Dependent Multi-Path routing. As can be seen from the darkened link arrows, additional paths to the destination router are available when using Source-Dependent Multi-Path routing rather than Source-Independent Single-Path routing method. Directed cycles are prevented because routing tables under Source-Dependent Multi-Path routing methods refer to both the source and the destination of an information packet to determine the next hop.
However, in a network with thousands of nodes, Source-Dependent Multi-Path routing presents at least two obstacles. Calculating a set of best disjoint paths from every possible source node to every possible destination node can be computationally intractable. Further, the memory requirements for storing a Source-Dependent Multi-Path routing table can be impractical.
FIG. 6 (Prior Art) shows a portion of a simplified Source-Dependent Multi-Path routing table 600 for node E 505 of FIG. 5 (Prior Art). The source-dependent entries cause the routing table 600 to balloon in size, even in our small example network of only eight routers. In a real network of thousands of routers and hundreds of thousands of destination addresses, the Source-Dependent Multi-Path routing table can approach terabyte size.